//
// Created by 孙代宇 on 2021/11/18.
//

#ifndef UNTITLED2_LIST_H
#define UNTITLED2_LIST_H

#include "stdio.h"
#include "stdlib.h"
#define INIT_SIZE  8

class List {

    typedef struct{
        int *data;
        int MAX_SIZE;
        int length;
    }SQList;

    void InitSQList(SQList &l){
        l.data = (int *)malloc(INIT_SIZE * sizeof (int));
        l.length = 0;
        int n = INIT_SIZE - 1;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        l.MAX_SIZE = (n < 0) ? 1 :  n + 1;
        // 防止违规操作获取到脏数据
        for (int i = 0; i < INIT_SIZE; ++i) {
            l.data[i] = 0;
        }
        l.length = 0;
    }

    void IncreaseSize(SQList &l, int len){
        int *p = l.data;
        l.data = (int *)malloc(INIT_SIZE + len * sizeof (int));
        for (int i = 0; i < l.length; ++i) {
            l.data[i] = p[i];
        }
//    printf("触发扩容，扩容前理想最大容量%d，扩容后理想最大容量%d\n", l.MAX_SIZE, len);
        l.MAX_SIZE = len;
        free(p);
    }

    int DeleteElement(int index){
        if (0 > index || index - 1 > l.length)
            return false;
        for (int i = index; i < l.length; i++)
            l.data[i] = l.data[i+1];
        l.length --;
    }
    int PeekElement(int index){
        return l.data[index];
    }

    bool InsertElement(int value, int index){
        if (0 > index || index - 1 > l.length)
            return false;
        if (l.MAX_SIZE * 0.75 < l.length)
            IncreaseSize(l, l.MAX_SIZE * 2);
        for (int i = l.length; i > index; i--)
            l.data[i] = l.data[i-1];
        l.data[index] = value;
        l.length ++;
        return true;
    }

public:
    SQList l;
};


#endif //UNTITLED2_LIST_H
